package foundation.Hexadecimal_to_octal_number;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String[] str = new String[n];
        for (int i = 0; i < n; i++) {
            str[i] = scanner.next();
        }
        for (int i = 0; i < n; i++) {
            System.out.println(count(str[i]));
        }
    }

    /**
     * 输出十进制数字的八进制形式
     * @param str 十进制数字
     * @return
     */
    public static String count(String str) {
        Map<Character, String> map = new HashMap<>();
        map.put('0', "0000");
        map.put('1', "0001");
        map.put('2', "0010");
        map.put('3', "0011");
        map.put('4', "0100");
        map.put('5', "0101");
        map.put('6', "0110");
        map.put('7', "0111");
        map.put('8', "1000");
        map.put('9', "1001");
        map.put('A', "1010");
        map.put('B', "1011");
        map.put('C', "1100");
        map.put('D', "1101");
        map.put('E', "1110");
        map.put('F', "1111");
        char[] arr = str.toCharArray();
        // 先将十六进制数字转为二进制
        StringBuilder num = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            num.append(map.get(str.charAt(i)));
        }
        // 若长度不是三的整数倍在左边补零
        if (num.length() % 3 != 0) {
            int len = num.length();
            for (int i = 0; i < 3 - len % 3; i++) {
                num.insert(0, 0);
            }
        }
        // 将二进制转为八进制数字输出
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = num.length() - 1; i >= 2; i -= 3) {
            stringBuilder.append(Character.getNumericValue(num.charAt(i - 2)) * 4
                                    + Character.getNumericValue(num.charAt(i - 1)) * 2
                                        + Character.getNumericValue(num.charAt(i)));
        }
        // 去除掉前面的零
        while (stringBuilder.charAt(stringBuilder.length() - 1) == '0') {
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        }
        return stringBuilder.reverse().toString();
    }
}
